package com.hackerank.arrays.map;

import java.util.HashMap;
import java.util.Map;

/**
 * Two Strings
 * 给你两个字符串和，找出是否存在一个字符串同时出现在和中。
 *
 * Input Format
 *
 * 一个文件中将给你一些测试数据。输入的第一行将包含一个整数，测试数据组数。
 *
 * 然后将有组测试数据的描述。 每个描述包含两行，第一行包含字符串，第二行包含字符串。
 *
 * Output Format
 *
 * 对每组测试数据，如果有公共子串，输出 "YES"。如果没有公共子串，输出"NO"。
 *
 * 约束条件
 *
 * 所有的字符串只包含小写字母。
 *
 * https://www.hackerrank.com/challenges/two-strings/problem?h_l=interview&playlist_slugs%5B%5D=interview-preparation-kit&playlist_slugs%5B%5D=dictionaries-hashmaps
 *
 * 解题思路：
 *  由于只有小写字母，所有两个串中出现出现的字符数不大于26个。建立长度为26的Map即可
 *
 *  时间复杂度 O(m + n)
 *  空间复杂度 O(26)
 * **/

public class TwoStrings {
    static String twoStrings(String s1, String s2) {
        Map<Character,Integer> map = new HashMap<Character,Integer>();

        for(int i=0;i<s1.length();i++){
            Character c = s1.charAt(i);
            map.put(c,1);
            if(map.size() == 26)
                break;
        }

        for(int i=0;i<s2.length();i++){
            Character c = s2.charAt(i);
            if(map.get(c) != null){
                return "YES";
            }
        }
        return "NO";
    }
}
